// 文件名：priority_queue_dijkstra.cpp
// 目的：使用优先队列实现 Dijkstra 单源最短路径算法（非负权图）。
// 要点：
//   - dist[v]：记录源点到各点的当前最短距离，初始化为 INF，源点为 0；
//   - 最小堆（distance, vertex）：每次取出当前距离最小的未确定节点；
//   - 松弛：对 u 的每条边 (u->v, w)，若 d + w 改善 dist[v]，则更新并将新对入堆；
//   - 跳过“过期条目”：当堆顶 d != dist[u] 时说明已有更短路径入堆，直接 continue。
// 复杂度：O((V + E) log V)（二叉堆实现）。
// 注意：
//   - 仅适用于边权非负；若有负权需使用 Bellman-Ford 或 Johnson 算法等。

#include <cstddef>
#include <iostream>
#include <limits>
#include <queue>
#include <vector>

struct Edge {
    std::size_t to;
    int weight;
};

using Graph = std::vector<std::vector<Edge>>;

std::vector<int> dijkstra(const Graph& graph, std::size_t source) {
    const int INF = std::numeric_limits<int>::max();
    std::vector<int> dist(graph.size(), INF);

    using Node = std::pair<int, std::size_t>; // (distance, vertex)
    struct Compare {
        bool operator()(const Node& a, const Node& b) const noexcept {
            return a.first > b.first; // 最小堆
        }
    };

    std::priority_queue<Node, std::vector<Node>, Compare> pq;
    dist[source] = 0;
    pq.emplace(0, source);

    while (!pq.empty()) {
        auto [d, u] = pq.top();
        pq.pop();

        if (d != dist[u]) {
            continue; // 跳过过期条目
        }

        for (const auto& edge : graph[u]) {
            int nd = d + edge.weight;
            if (nd < dist[edge.to]) {
                dist[edge.to] = nd;
                pq.emplace(nd, edge.to);
            }
        }
    }

    return dist;
}

int main() {
    Graph graph = {
        {{1, 4}, {2, 1}},
        {{3, 1}},
        {{1, 2}, {3, 5}},
        {}
    };

    auto dist = dijkstra(graph, 0);
    for (std::size_t i = 0; i < dist.size(); ++i) {
        std::cout << "dist[0 -> " << i << "] = " << dist[i] << '\n';
    }
    return 0;
}